/**
 *  Merge Sort
 *
 *  Time complexity: O(nlogn)
 *  Space complexity: O(n)
 */

class MergeSort<E extends Comparable<E>> {

    public void sort(E[] a, int lo, int hi) {
        // Base case
        if (lo >= hi) return;

        int mid = lo + (hi - lo) / 2;

        // Sort the left half
        sort(a, lo, mid);
        // Sort the right half
        sort(a, mid + 1, hi);
        // Merge left half and right half
        merge(a, lo, mid, hi);
    }

    private void merge(E[] a, int lo, int mid, int hi) {
        int i, j, k;
        int N = a.length;
        E[] aux = (E[]) new Comparable[N];
        
        // Copy a[] to aux[]
        for (i = 0; i < N; i++) {
            aux[i] = a[i];
        }

        i = lo;
        j = mid + 1;

        for (k = lo; k <= hi; k++) {
            if (i > mid) { // Left half is exhausted
                a[k] = aux[j++];
            } else if (j > hi) { // Right half is exhausted
                a[k] = aux[i++];
            } else if (aux[j].compareTo(aux[i]) < 0) { // Right < left
                a[k] = aux[j++];
            } else { // Left < right
                a[k] = aux[i++];
            }
        }
    }

}
